type 'a binary_tree =
  | Empty
  | Node of 'a * 'a binary_tree * 'a binary_tree   (* 当前节点 ，当前左子树，当前右子树 *)
;;

let example_layout_tree =
  let leaf x = Node (x, Empty, Empty) in
  Node ('n', Node ('k', Node ('c', leaf 'a',
                           Node ('h', Node ('g', leaf 'e', Empty), Empty)),
                 leaf 'm'),
       Node ('u', Node ('p', Empty, Node ('s', leaf 'q', Empty)), Empty))
;;

(* 
自左向右顺序布局, 空间紧凑性极高（x 连续，无空隙）
depth：当前节点的深度（根为 1）。
x_left：当前子树可以使用的最左 x 坐标（即从这个 x 开始向右分配位置）。 
l'：布局后的左子树。
l_x_max：左子树最右边使用的 x 坐标（即左子树占据的 x 范围是 [x_left, l_x_max]）
r'：布局后的右子树。
r_x_max：右子树最右边的 x 坐标（即整棵子树的最右 x)

(Node ((v, l_x_max, depth), l', r'), r_x_max) 构造当前节点的布局版本：
节点值变为 (v, x, y) = (v, l_x_max, depth)。
x 坐标取左子树最右位置 l_x_max → 这样根节点位于左子树的“右侧边缘”，保证不会与左子树重叠。
y 坐标就是当前深度 depth。
整个子树的最右 x 坐标是 r_x_max（因为右子树在最右边）。

fst 取返回元组的第一个元素（即布局后的树，忽略最后的 r_x_max）
*)

let layout_binary_tree_1 t =
  let rec layout depth x_left = function
    | Empty -> (Empty, x_left)
    | Node (v,l,r) ->
       let (l', l_x_max) = layout (depth + 1) x_left l in
       let (r', r_x_max) = layout (depth + 1) (l_x_max + 1) r in
         (Node ((v, l_x_max, depth), l', r'), r_x_max)
  in
    fst (layout 1 1 t);;

layout_binary_tree_1 example_layout_tree;;